{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Earnings From Taxi"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #dynamic-programming #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #动态规划 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxTaxiEarnings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #出租车的最大盈利"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你驾驶出租车行驶在一条有 <code>n</code>&nbsp;个地点的路上。这 <code>n</code>&nbsp;个地点从近到远编号为&nbsp;<code>1</code>&nbsp;到&nbsp;<code>n</code>&nbsp;，你想要从 <code>1</code>&nbsp;开到 <code>n</code>&nbsp;，通过接乘客订单盈利。你只能沿着编号递增的方向前进，不能改变方向。</p>\n",
    "\n",
    "<p>乘客信息用一个下标从 <strong>0</strong>&nbsp;开始的二维数组&nbsp;<code>rides</code>&nbsp;表示，其中&nbsp;<code>rides[i] = [start<sub>i</sub>, end<sub>i</sub>, tip<sub>i</sub>]</code>&nbsp;表示第&nbsp;<code>i</code>&nbsp;位乘客需要从地点&nbsp;<code>start<sub>i</sub></code>&nbsp;前往&nbsp;<code>end<sub>i</sub></code>&nbsp;，愿意支付&nbsp;<code>tip<sub>i</sub></code>&nbsp;元的小费。</p>\n",
    "\n",
    "<p><strong>每一位</strong> 你选择接单的乘客&nbsp;<code>i</code>&nbsp;，你可以 <strong>盈利</strong>&nbsp;<code>end<sub>i</sub> - start<sub>i</sub> + tip<sub>i</sub></code>&nbsp;元。你同时&nbsp;<strong>最多</strong>&nbsp;只能接一个订单。</p>\n",
    "\n",
    "<p>给你 <code>n</code>&nbsp;和 <code>rides</code>&nbsp;，请你返回在最优接单方案下，你能盈利&nbsp;<strong>最多</strong>&nbsp;多少元。</p>\n",
    "\n",
    "<p><strong>注意：</strong>你可以在一个地点放下一位乘客，并在同一个地点接上另一位乘客。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>n = 5, rides = [<em><strong>[2,5,4]</strong></em>,[1,5,1]]\n",
    "<b>输出：</b>7\n",
    "<b>解释：</b>我们可以接乘客 0 的订单，获得 5 - 2 + 4 = 7 元。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>n = 20, rides = [[1,6,1],<strong><em>[3,10,2]</em></strong>,<em><strong>[10,12,3]</strong></em>,[11,12,2],[12,15,2],<strong><em>[13,18,1]</em></strong>]\n",
    "<b>输出：</b>20\n",
    "<b>解释：</b>我们可以接以下乘客的订单：\n",
    "- 将乘客 1 从地点 3 送往地点 10 ，获得 10 - 3 + 2 = 9 元。\n",
    "- 将乘客 2 从地点 10 送往地点 12 ，获得 12 - 10 + 3 = 5 元。\n",
    "- 将乘客 5 从地点 13 送往地点 18 ，获得 18 - 13 + 1 = 6 元。\n",
    "我们总共获得 9 + 5 + 6 = 20 元。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= rides.length &lt;= 3 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>rides[i].length == 3</code></li>\n",
    "\t<li><code>1 &lt;= start<sub>i</sub> &lt; end<sub>i</sub> &lt;= n</code></li>\n",
    "\t<li><code>1 &lt;= tip<sub>i</sub> &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-earnings-from-taxi](https://leetcode.cn/problems/maximum-earnings-from-taxi/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-earnings-from-taxi](https://leetcode.cn/problems/maximum-earnings-from-taxi/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5\\n[[2,5,4],[1,5,1]]', '20\\n[[1,6,1],[3,10,2],[10,12,3],[11,12,2],[12,15,2],[13,18,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\n",
    "        dp=[0]*(n+1)\n",
    "        rides.sort(key=lambda x:-x[1])\n",
    "        for i in range(1,n+1):\n",
    "            if rides and rides[-1][1]>i:\n",
    "                dp[i]=dp[i-1]\n",
    "            else:\n",
    "                while rides and rides[-1][1]==i:\n",
    "                    temp=rides.pop()\n",
    "                    dp[i]=max(dp[i],dp[i-1],dp[temp[0]]+i-temp[0]+temp[2])\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\n",
    "        rides.sort(key=lambda x:(x[1], x[0]))\n",
    "        ans = [0] * (n+1)\n",
    "\n",
    "        a = 0\n",
    "        bb = None\n",
    "        for i in range(1,n+1):\n",
    "            if bb is None:\n",
    "                bb = i \n",
    "            else:\n",
    "                if bb is not None:\n",
    "                    if bb != i:\n",
    "                        ans[i] = ans[bb] \n",
    "                        bb = i\n",
    "            while rides and i == rides[0][1]:\n",
    "                starti, endi, tipi = rides[0]\n",
    "                ans[i] = max(ans[i], endi - starti + tipi + ans[starti])\n",
    "                rides.pop(0)\n",
    "        return ans[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\n",
    "        rides.sort(key=lambda x:x[1])\n",
    "        n = len(rides)\n",
    "        dp = [0] * (len(rides)+1)\n",
    "        for i in range(1, n+1):\n",
    "            p = bisect_right(rides, rides[i-1][0], key = lambda x:x[1])\n",
    "            dp[i] = max(dp[i-1], dp[p] + rides[i-1][2] + rides[i-1][1]-rides[i-1][0])\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\n",
    "        d = {}\n",
    "        for r in rides:\n",
    "            if r[1] not in d: d[r[1]] = []\n",
    "            d[r[1]].append(r)\n",
    "\n",
    "        f = [0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            f[i] = f[i-1]\n",
    "            if i not in d: continue\n",
    "            for r in d[i]:\n",
    "                f[i] = max(f[i], f[r[0]]+r[1]-r[0]+r[2])\n",
    "        return f[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\n",
    "        dic = defaultdict(list)\n",
    "        for x in rides:\n",
    "            dic[x[1]].append([x[0],x[2]])\n",
    "        dp = [0 for _ in range(n + 1)]\n",
    "        for i in range(2, n + 1):\n",
    "            income = max(dp[x[0]] + i - x[0] + x[1] for x in dic.get(i,[[i,0]]))\n",
    "            dp[i] = max(dp[i - 1],income)\n",
    "        \n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\n",
    "        # 按照终点进行分组\n",
    "        groups = [[] for _ in range(n+1)]\n",
    "        for s,e,t in rides:\n",
    "            groups[e].append((s,e-s+t))\n",
    "        dp = [0 for _ in range(n+2)] \n",
    "        for end, group in enumerate(groups):\n",
    "            dp[end+1] = dp[end]\n",
    "            if group:\n",
    "                for s, t in group:\n",
    "                    dp[end+1] = max(dp[end+1],dp[s+1] + t)\n",
    "        # print(dp)\n",
    "        return dp[n+1] \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\n",
    "        record = [[] for _ in range(n+1)]\n",
    "        for i,j,v in rides:\n",
    "            record[j].append([i,j-i+v])\n",
    "        dp =[0 for _ in range(n+1)]\n",
    "        for i in range(1,n+1):\n",
    "            dp[i] = dp[i-1]\n",
    "            for start,v in record[i]:\n",
    "                dp[i] = max(dp[i],dp[start]+v)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\n",
    "        # 按照终点进行分组\n",
    "        groups = [[] for _ in range(n+1)]\n",
    "        for s,e,t in rides:\n",
    "            groups[e].append((s,e-s+t))\n",
    "        dp = [0 for _ in range(n+2)] \n",
    "        for end, group in enumerate(groups):\n",
    "            dp[end+1] = dp[end]\n",
    "            if group:\n",
    "                for s, t in group:\n",
    "                    dp[end+1] = max(dp[end+1],dp[s+1] + t)\n",
    "        print(dp)\n",
    "        return dp[n+1] \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\n",
    "        sav = collections.defaultdict(list)\n",
    "        for i in rides:\n",
    "            sav[i[1]].append([i[0],i[2]])\n",
    "        dic = collections.defaultdict(int)\n",
    "        for i in range(1,n+1):\n",
    "            dic[i]=dic[i-1]\n",
    "            if not i in sav:\n",
    "                continue\n",
    "            for j in sav[i]:\n",
    "                dic[i]=max(dic[i],dic[j[0]]+i-j[0]+j[1])\n",
    "        return dic[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\n",
    "        vis = collections.defaultdict(list)\n",
    "        for i in rides:\n",
    "            vis[i[1]].append(i)\n",
    "        target = sorted(i[1] for i in rides)\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(2, n + 1):\n",
    "            dp[i] = dp[i - 1]\n",
    "            for j in vis[i]:\n",
    "                idx = bisect.bisect_left(target, j[0])  # 二分法找最靠近当前区间左侧的合法区间\n",
    "                temp = target[idx] if j[0] >= target[idx] else target[idx - 1] if idx > 0 else 0\n",
    "                dp[i] = max(dp[i], dp[temp] + j[1] - j[0] + j[2])\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\n",
    "        end_2_rides_dict = defaultdict(list)\n",
    "        for ride in rides:\n",
    "            end_2_rides_dict[ride[1]].append(ride)\n",
    "\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i] = dp[i - 1]\n",
    "            for start, end, tip in end_2_rides_dict[i]:\n",
    "                dp[i] = max(dp[i], end - start + tip + dp[start])\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\n",
    "        dp = [0] * (n+1)\n",
    "        # dp[i]代表考虑开到编号为 i 的地点的时，能赚到最多钱\n",
    "        # 也就是说，如果这里是接单到的，dp[end_i] = dp[start_i] + (end - start + tip_i) 对于所有end_i等于i来说取max\n",
    "        # 如果不是dp[i] = dp[i - 1]\n",
    "        \n",
    "        # 记录end和订单的哈希表\n",
    "        mydict = defaultdict(list)\n",
    "        for rid, (start, end, tip) in enumerate(rides):\n",
    "            mydict[end].append((start, tip))\n",
    "        \n",
    "        for i in range(1, n+1):\n",
    "            dp[i] = dp[i - 1]\n",
    "            for start, tip in mydict[i]:\n",
    "                dp[i] = max(dp[i], dp[start] + i - start + tip)\n",
    "        \n",
    "        return dp[-1]\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\n",
    "        mx = [0] * (n)\n",
    "        end_dict = defaultdict(list)\n",
    "        for s, e, t in rides:\n",
    "            end_dict[e-1].append((s-1, t))\n",
    "        dp = [0] * n\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if len(end_dict[i]) == 0:\n",
    "                dp[i] = mx[i-1]\n",
    "                mx[i] = mx[i-1]\n",
    "            else:\n",
    "                dp[i] = dp[i-1]\n",
    "                mx[i] = mx[i-1]\n",
    "                for s, t in end_dict[i]:\n",
    "                    dp[i] = max(dp[i], dp[s]+i-s+t)\n",
    "                mx[i] = max(dp[i], mx[i-1])\n",
    "        return dp[n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\n",
    "        # 接了 [starti, endi, tipi], 则最大为 dp[starti]+endi - starti + tipi\n",
    "        dp = [0]*n\n",
    "        d=defaultdict(list)\n",
    "        # rides.sort()\n",
    "        for starti, endi, tipi in rides:\n",
    "            d[endi-1].append([starti-1, endi-1, tipi])\n",
    "        for i in range(1,n):\n",
    "            dp[i] = dp[i-1]  # 不接d[i]反而可能收益更大\n",
    "            for starti, endi, tipi in d[i]:\n",
    "                dp[endi] = max(dp[endi], dp[starti]+endi - starti + tipi)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict \n",
    "class Solution:\n",
    "    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\n",
    "        global memo \n",
    "        global ends\n",
    "        # dp[i] = max(dp[i-1], rides[j] ending at i)\n",
    "        memo = {}\n",
    "        ends = defaultdict(lambda: [])\n",
    "        for ride in rides:\n",
    "            ends[ride[1]].append(ride)\n",
    "        for i in range(1,n+1):\n",
    "            dp(i)\n",
    "        return dp(n)\n",
    "\n",
    "memo = {}\n",
    "ends = {}\n",
    "def dp(i: int) -> int:\n",
    "    global memo \n",
    "    global ends \n",
    "    if i in memo:\n",
    "        return memo[i]\n",
    "    # base case \n",
    "    if i == 1 or i == 0:\n",
    "        memo[i] = 0 \n",
    "        return memo[i]\n",
    "    # typical cases \n",
    "    res = dp(i-1)\n",
    "    for ride in ends[i]:\n",
    "        start = ride[0]\n",
    "        tip = ride[2]\n",
    "        res = max(res, dp(start) + i - start + tip)\n",
    "    # save result \n",
    "    memo[i] = res \n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\n",
    "        trips = []\n",
    "        for u, v, w in rides:\n",
    "            trips.append((u, v, v - u + w))\n",
    "        trips.sort()\n",
    "        table = {}\n",
    "        val = self.search(0, trips, table)\n",
    "        return val\n",
    "        \n",
    "    def search(self, pos, trip, table):\n",
    "        if pos not in table:\n",
    "            idx = self.find(trip, pos)\n",
    "            m = len(trip)\n",
    "            res = 0\n",
    "            for i in range(idx, m):\n",
    "                if trip[i][0] == trip[idx][0]:\n",
    "                    res = max(res, self.search(trip[i][1], trip, table) + trip[i][2])\n",
    "                else:\n",
    "                    res = max(res, self.search(trip[i][0], trip, table))\n",
    "                    break\n",
    "            table[pos] = res\n",
    "        return table[pos]\n",
    "    \n",
    "    def find(self, trip, pos):\n",
    "        n = len(trip)\n",
    "        l, r = 0, n - 1\n",
    "        if pos > trip[r][0]: return n\n",
    "        if pos < trip[l][0]: return 0\n",
    "        while l + 1 < r:\n",
    "            m = (l + r) // 2\n",
    "            if trip[m][0] > pos:\n",
    "                r = m\n",
    "            elif trip[m][0] < pos:\n",
    "                l = m\n",
    "            else:\n",
    "                r = m\n",
    "        if trip[l][0] == pos:\n",
    "            return l\n",
    "        else:\n",
    "            return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\n",
    "        g = defaultdict(set)\n",
    "        for s, t, pay in rides:\n",
    "            g[s].add((t, pay))\n",
    "        dp = [0] * (n + 1)\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i] = max(dp[i], dp[i - 1])\n",
    "            for j, pay in g[i]:\n",
    "                if j <= i:\n",
    "                    continue\n",
    "                t = j - i + pay + dp[i]\n",
    "                dp[j] = max(dp[j - 1], t, dp[j])\n",
    "                ans = max(ans, dp[j])\n",
    "                # print(i, j)\n",
    "                # print(t, dp[j], ans)\n",
    "        # print(dp[1:])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\r\n",
    "        # group the rides according to end position\r\n",
    "        profit = {i: [(i - 1, 0)] for i in range(1, n)}\r\n",
    "        for start, end, tip in rides:\r\n",
    "            profit[end - 1].append((start - 1, end - start + tip))\r\n",
    "        \r\n",
    "        dp = [0] * n\r\n",
    "        for i in range(1, n):\r\n",
    "            for start, p in profit[i]:\r\n",
    "                dp[i] = max(dp[i], dp[start] + p)\r\n",
    "        \r\n",
    "        return dp[n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\n",
    "        rides.sort()\n",
    "        @cache\n",
    "        def dfs(j):            \n",
    "            idx = bisect_left(rides, [j, 0, 0])\n",
    "            if idx >= len(rides): return 0\n",
    "            maxl = 0\n",
    "            s0, e0, t0 = rides[idx]\n",
    "            for i in range(idx, len(rides)):\n",
    "                start, end, tip = rides[i]\n",
    "                e0 = min(e0, end)\n",
    "                if start >= e0: break\n",
    "                maxl = max(maxl, dfs(end) + end - start + tip)\n",
    "            return maxl\n",
    "        return dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx):\n",
    "            if idx == len(rides):  # base case\n",
    "                return 0\n",
    "            start, end, tip = rides[idx]\n",
    "            j = bisect.bisect_left(rides, end, key=lambda x: x[0])\n",
    "            choose = dfs(j) + (end - start + tip)\n",
    "            not_choose = dfs(idx + 1)\n",
    "            return max(choose, not_choose)\n",
    "        \n",
    "        rides.sort()\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\n",
    "        rides.sort(key=lambda x:x[1])\n",
    "        lst = [x[1] for x in rides]\n",
    "        n=len(rides)\n",
    "        @lru_cache(None)\n",
    "        def dp(i):\n",
    "            if i >= n or i < 0:\n",
    "                return 0\n",
    "            start, end, value = rides[i]\n",
    "            idx = bisect_right(lst, start) - 1\n",
    "            max_v = dp(idx) + value+(end-start)\n",
    "            v2 = dp(i - 1)\n",
    "            return max(v2, max_v)\n",
    "\n",
    "        return dp(n - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\n",
    "        rides.sort(key=lambda x: (x[1], x[0]))\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i < 0: return 0\n",
    "            s, e, t = rides[i]\n",
    "            res1 = dfs(i - 1)\n",
    "            j = bisect_right(rides, s, key=lambda x:x[1]) - 1\n",
    "            res2 = t + (e - s) + dfs(j)\n",
    "            return res1 if res1 >= res2 else res2\n",
    "        return dfs(len(rides) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\n",
    "        m = len(rides)\n",
    "        rides.sort()\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx):\n",
    "            if idx == m:\n",
    "                return 0\n",
    "            \n",
    "            s, e, t = rides[idx]\n",
    "            nxt = bisect_left(rides, [e, -1, -1])\n",
    "            return max(dfs(idx + 1), e - s + t + dfs(nxt))\n",
    "        \n",
    "        ans = dfs(0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\n",
    "        rides.sort()\n",
    "        lefts = [l for l, r, v in rides]\n",
    "        \n",
    "        @cache\n",
    "        def f(i):\n",
    "            if i >= len(rides):\n",
    "                return 0\n",
    "            ans = f(i+1)\n",
    "            l, r, v = rides[i]\n",
    "            j = bisect_left(lefts, r)\n",
    "            ans = max(ans, v+r-l+f(j))\n",
    "            return ans\n",
    "        \n",
    "        return f(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\n",
    "        rides.sort()\n",
    "        def bisect(x, l):\n",
    "            r = len(rides)\n",
    "            while l < r:\n",
    "                m = l + (r - l)//2\n",
    "                if rides[m][0] < x:\n",
    "                    l = m + 1\n",
    "                else:\n",
    "                    r = m\n",
    "            return l\n",
    "        @lru_cache(10**5)\n",
    "        def dfs(i = 0):\n",
    "            if i == len(rides):return 0\n",
    "            v = rides[i][1] - rides[i][0] + rides[i][2]\n",
    "            j = bisect(rides[i][1], i + 1)\n",
    "            return max(dfs(i + 1), v + dfs(j))\n",
    "        return dfs()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict \n",
    "class Solution:\n",
    "    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\n",
    "        global memo \n",
    "        global ends\n",
    "        # dp[i] = max(dp[i-1], rides[j] ending at i)\n",
    "        memo = {}\n",
    "        ends = defaultdict(lambda: [])\n",
    "        for ride in rides:\n",
    "            ends[ride[1]].append(ride)\n",
    "        \n",
    "        return dp(n)\n",
    "\n",
    "memo = {}\n",
    "ends = {}\n",
    "def dp(i: int) -> int:\n",
    "    global memo \n",
    "    global ends \n",
    "    if i in memo:\n",
    "        return memo[i]\n",
    "    # base case \n",
    "    if i == 1 or i == 0:\n",
    "        memo[i] = 0 \n",
    "        return memo[i]\n",
    "    # typical cases \n",
    "    res = dp(i-1)\n",
    "    for ride in ends[i]:\n",
    "        start = ride[0]\n",
    "        tip = ride[2]\n",
    "        res = max(res, dp(start) + i - start + tip)\n",
    "    # save result \n",
    "    memo[i] = res \n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\n",
    "        d = dict()\n",
    "        end = 0\n",
    "        for s,e,c in rides:\n",
    "            if e not in d:\n",
    "                d[e] = list()\n",
    "            d[e].append((s, c))\n",
    "            end = max(end, e)\n",
    "        cache = dict()\n",
    "        def f(e):\n",
    "            if e in cache:\n",
    "                return cache[e]\n",
    "            if e == 0:\n",
    "                return 0\n",
    "            if e not in d:\n",
    "                cache[e] = f(e-1)\n",
    "                return cache[e]\n",
    "            tmp = 0\n",
    "            for s,c in d[e]:\n",
    "                tmp = max(tmp, f(s)+(e-s+c))\n",
    "            tmp = max(tmp, f(e-1))\n",
    "            cache[e] = tmp\n",
    "            return tmp\n",
    "        return f(end)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaxiEarnings(self, n, rides):\n",
    "        def dfs(pos):\n",
    "            if dp[pos] != -1:\n",
    "                return dp[pos]\n",
    "            ans = 0\n",
    "            for pre, add in arrive[pos]:\n",
    "                ans = max(ans, dfs(pre) + add)\n",
    "            \n",
    "            dp[pos] = max(ans, dfs(pos-1))\n",
    "            \n",
    "            return dp[pos]\n",
    "\n",
    "        dp = [-1] * (n+1)\n",
    "        dp[0] = 0\n",
    "        arrive = [[] for _ in range(n+1)]\n",
    "        for start, end, tip in rides:\n",
    "            arrive[end].append((start, end-start+tip))\n",
    "        \n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\n",
    "\n",
    "        from collections import defaultdict\n",
    "        dic=defaultdict(list)\n",
    "\n",
    "        for r in rides: dic[r[1]].append(r)\n",
    "\n",
    "        from functools import lru_cache\n",
    "        @lru_cache(None)\n",
    "        def dp(n):\n",
    "            if n==0: return 0\n",
    "            if n not in dic: return dp(n-1)\n",
    "            else:\n",
    "                v=0\n",
    "                for r in dic[n]: v=max(v,dp(n-1),dp(r[0])+r[1]-r[0]+r[2])\n",
    "                return v\n",
    "\n",
    "        return dp(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\n",
    "\n",
    "        from collections import defaultdict\n",
    "        dic=defaultdict(list)\n",
    "\n",
    "        for r in rides: dic[r[1]].append(r)\n",
    "\n",
    "        from functools import lru_cache\n",
    "        @lru_cache(None)\n",
    "        def dp(n):\n",
    "            if n==0: return 0\n",
    "            if n not in dic: return dp(n-1)\n",
    "            else:\n",
    "                v=0\n",
    "                for r in dic[n]: v=max(v,dp(n-1),dp(r[0])+r[1]-r[0]+r[2])  #dp(n-1)表示在当前这个站能上车但是不上车\n",
    "                return v\n",
    "\n",
    "        return dp(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\n",
    "\n",
    "        mp = collections.defaultdict(list)\n",
    "        for start, end, tip in rides:\n",
    "            mp[end].append((start, tip))\n",
    "\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(i):\n",
    "            # base\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            res = dp(i - 1)\n",
    "\n",
    "            if i in mp:\n",
    "                for start, tip in mp[i]:\n",
    "                    res = max(res, dp(start) + i - start + tip)\n",
    "\n",
    "            return res\n",
    "\n",
    "        return dp(n)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\n",
    "        d = defaultdict(list)\n",
    "        for x, y, v in rides:\n",
    "            d[x].append([y, v])\n",
    "        @cache  \n",
    "        def f(j):\n",
    "            if j>n:\n",
    "                return 0\n",
    "            ans = f(j + 1)\n",
    "            if j in d:\n",
    "                for y, v in d[j]:\n",
    "                    ans = max(ans, v + f(y) + y - j)\n",
    "            return ans\n",
    "        return f(0)\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
